package com.hardy.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/**
 * Author: Hardy
 * Date:   2020/9/9
 * Description:
 **/
public class Que39 {

    public static void main(String[] args) {

        int[] candidates = {4, 2, 8};
        int target = 8;

        System.out.println(new Solution().combinationSum(candidates, target));
    }

    static class Solution {

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new LinkedList<>();

            Arrays.sort(candidates);

            df(res, new ArrayList<>(), 0, 0, candidates, target);
            return res;
        }

        private List<Integer> df(List<List<Integer>> res, List<Integer> cm, int sum, int i, int[] candidates, int target) {
            for (; i < candidates.length; i++) {
                // 结果收集
                sum += candidates[i];

                // 剪枝中断
                if (sum == target) {
                    cm.add(candidates[i]);
                    res.add(cm);
                    return new ArrayList<>(cm.subList(0, cm.size() - 1));
                }

                // 剪枝中断
                if (sum > target) return cm;

                // 搜索
                cm.add(candidates[i]);
                cm = df(res, cm, sum, i, candidates, target);

                // 结果回溯
                sum -= candidates[i];
                cm.remove(cm.size() - 1);
            }
            return cm;
        }

//        public List<List<Integer>> combinationSum(int[] candidates, int target) {
//            List<List<Integer>> res = new LinkedList<>();
//
//            df(res, new ArrayList<>(), 0, 0, candidates, target);
//
//            return res;
//        }
//
//        private List<Integer> df(List<List<Integer>> res, List<Integer> cm, int sum, int i, int[] candidates, int target) {
//            for (; i < candidates.length; i++) {
//                // 结果收集
//                sum += candidates[i];
//                cm.add(candidates[i]);
//
//                // 剪枝中断
//                if (sum == target) {
//                    res.add(cm);
//                    cm = new ArrayList<>(cm);
//                }
//
//                // 剪枝中断
//                if (sum < target) {
//                    // 搜索
//                    cm = df(res, cm, sum, i, candidates, target);
//                }
//
//                // 结果回溯
//                sum -= candidates[i];
//                cm.remove(cm.size() - 1);
//            }
//            return cm;
//        }
    }
}
